| AFiles: Installieren (Teil2) | WGet | Effizientes Programmieren (Teil2) |

Effizientes Programmieren - Kurs 2

Diesmal wagen wir uns an eine interessante Anwendung heran, dem Berechnen von mathematischen Ausdrücken. Dieses auf den ersten Blick sehr schwierige Problem läßt sich mit einer sehr wichtigen Datenstruktur - dem Stapel - auf relativ einfache Weise lösen.

In der letzten Ausgabe haben wir uns mit den linearen Listen beschäftigt. Dabei wurden die Operationen Einfügen, Entfernen und Suchen genauer behandelt. Heute wollen wir uns mit einer Abart von Listen befassen, den Stapel (Stack), die eigentlich nur Listen mit beschränkten Zugriffsrechten sind. Anders ausgedrückt handelt es sich dabei um eine den Listen verwandte Datenstruktur, auf der andere Operationen definiert wurden. Um zu demonstrieren, was mit diesem sehr gebräuchlichen Datentyp alles möglich ist, werden wir uns heute mit einer sicherlich interessanten Anwendung beschäftigen, nämlich der Berechnung von in Strings gespeicherten Termen. Wir wollen eine Routine entwickeln, der wir beispielsweise den String "2+3*4" übergeben können und die dann als Ergebnis 14 zurückgibt. Für diese Anwendung sind die Stapel sehr geeignet.

Zuerst werden wir einmal definieren, was wir unter einem Stapel verstehen. Ein Stapel ist eine sehr wichtige und mächtige Datenstruktur in der Informatik und wird auch dementsprechend oft eingesetzt. Am wichtigsten ist er als Prozessor-Stapel, mit dem wohl schon jeder Assembler-Programmierer Bekanntschaft gemacht haben wird. Aber auch für die Rekursion werden Stapel benützt.

Man unterscheidet grundsätzlich zwischen zwei verschiedenen Stapeltypen: dem LIFO-Stack und dem FIFO-Stack. Der Unterschied zwischen den beiden wird nach dem folgenden Beispiel sofort klar sein. Man veranschaulicht sich Stapel am besten anhand von Notizblättern, die aufeinandergelegt werden. Es können dabei immer nur Notizblätter oben auf den Stapel gelegt und niemals irgendwo dazwischen eingefügt werden. Ähnlich können sie auch nur an den Enden des Stapels wieder entnommen werden. Hier unterscheiden sich die bereits genannten LIFO und FIFO-Stapel.

LIFO steht für Last-In-First-Out, was bedeutet, daß das als letztes auf den Stapel gelegte Element als erstes wieder vom Stapel entfernt wird. Er ist der weitaus gebräuchlichere Stapeltyp, weshalb wir ihn im folgenden einfach nur den Stapel nennen werden. Der zweite Stapeltyp, FIFO, steht für First- In-First-Out. Hier wird das zuerst auf den Stapel gelegte Element (oder Notizblatt in unserem Beispiel) auch wieder als erstes vom Stapel entfernt. Er wird oft auch als Schlange oder Queue bezeichnet, denn wenn am einen Ende der Schlange Elemente angefügt und am anderen Ende ungefähr ebensoviele entfernt werden, dann sieht es so aus als "krieche" die Schlange im anfangs belegten Speicherbereich immer weiter nach hinten. Beide Stapeltypen lassen sich auf dieselbe Weise implementieren wie lineare Listen. Da die Elemente beim Stapel aber nur an einem Ende angehängt werden können, ist die Speicherung in einem Array die weitaus gebräuchlichere Form. Betrachten wir also einmal genauer, welche Operationen wir für die beiden Stapeltypen definieren wollen.

Wir benötigen neben dem Konstruktor und dem Destruktor, die den Speicherplatz für den Stapel zur Verfügung stellen bzw. wieder frei geben, die Operationen push, pop, top, clear und isempty. push legt ein Element auf den Stapel, pop holt das oberste wieder herunter (je nach Stapeltyp). Mit top kann das oberste Element des Stapels gelesen werden, ohne es vom Stapel zu entfernen. Mit clear kann ein bestehender Stapel auf einmal ganz geleert werden. isempty stellt hingegen eine Möglichkeit zur Verfügung, um festzustellen, ob der Stapel leer ist.

Die einfachste und schnellste Form, einen Stapel zu implementieren, ist ein Array aufzustellen, das die voraussichtlich maximale Elementanzahl, die auf dem Stapel Platz finden soll, aufnehmen kann. Da es aber oft schwer vorauszusagen ist, wie groß ein Stapel nun tatsächlich mindestens sein muß, kann es sein, daß entweder aus Vorsicht viel zuviel Speicher reserviert wurde oder der Stapel plötzlich unerwartet voll wird. Für die allgemeine Verwendung eines Stapel bietet sich deshalb ein sichererer, dynamischer Aufbau an.

Die Idee dabei ist, daß wir den Stapelspeicher immer blockweise allokieren und diese einzelnen Speicherblöcke in einer verketteten Liste speichern. Wenn nun der Stapel überläuft, belegen wir einfach einen neuen Speicherblock und hängen ihn an diese Liste an. Listing 1 stellt eine solche Implementation eines LIFO-Stapels dar. Diese Routinen können wir dann gleich bei unserer schon oben angesprochenen Beispielanwendung von Stapel verwenden, auf die ich nun genauer eingehen will.

Die Berechnung von beliebigen Formeln ist ein häufig auftretendes Problem. Eine typische Anwendung wäre ein Funktionsplotter oder eine Tabellenkalkulation, aber auch bei anderen Programmen erhöht sich der Komfort erheblich, wenn statt einfacher Zahleneingaben gleich ganze Terme akzeptiert werden. Da dieses Problem mithilfe von Stapel recht einfach gelöst werden kann, wollen wir uns hier einmal damit beschäftigen. Die Lösung erscheint auf den ersten Blick gar nicht so einfach, besonders wenn alle Rechengesetze eingehalten werden sollen. So sollen die Prioritäten der Operatoren und Klammern berücksichtigt werden. Um nun das Problem zu vereinfachen, wollen wir an dieser Stelle einige Begriffe erläutern.

Die Notation eines mathematischen Ausdrucks, wie wir ihn aus der Schule kennen, wie z.B. 2*(7+5), bezeichnet man als Infix-Notation. Das Gegenstück dazu heißt Postfix-Notation oder UPN (umgekehrte polnische Notation). In dieser, von einigen Programmiersprachen wie Forth oder Postscript verwendeten Schreibweise, werden zuerst die Operanden angeführt und anschließend der Operator, auf den sich die Operanden beziehen. Für das obige Beispiel würde eine entsprechende Postfix-Notation so lauten: 2 7 5 + *.

Stellen Sie sich nun vor, man würde die Zahlen auf einen LIFO-Stapel legen, sie beim Auftreten eines Operators verknüpfen und das Ergebnis wieder auf den Stapel legen. Bei unserem Beispiel würde das wie folgt lauten: lege 2 auf Stapel - lege 7 auf Stapel - lege 5 auf Stapel - hole 5 und 7 vom Stapel, addiere sie und lege das Ergebnis 7+5=12 auf den Stapel - hole 12 und 2 vom Stapel und multipliziere sie, dann lege Ergebnis wieder zurück - fertig.

Wie Sie sehen, ist die Berechnung von Postfix-Ausdrücken viel leichter zu programmieren, als dies für Infix-Terme der Fall ist. Außerdem benötigt die Postfix-Notation keine Klammern oder Prioritäten der Operatoren, da die Reihenfolge der Abarbeitung schon implizit durch den Ausdruck bestimmt wird. Ein weiterer Vorteil ist die schnellere Abarbeitung, verglichen mit der Infix-Darstellung. Leider ist diese Notation jedoch recht unüblich und man kann wohl keinem Anwender zumuten, daß er alle Eingaben in Postfix macht. Trotzdem reduziert sich unser Problem auf die Umwandlung von der Infix- in die Postfix-Notation.

Damit scheint auf den ersten Blick gar nicht viel gewonnen, wir werden aber sehen, daß mithilfe von LIFO-Stapel diese Konvertierung gar nicht so aufwendig ist, wie sie im ersten Moment zu sein scheint. Die Lösung ist nämlich verblüffend einfach.

Nehmen wir also einmal an, wir hätten zwei Stapel zur Verfügung, einen zum Speichern von Operatoren (Operator-Stapel) und einen zweiten für die auftretenden Zahlen (Werte-Stapel). Nun gehen wir unseren Infix-Term von links nach rechts durch und unterscheiden fünf Fälle:
(1) Wir stoßen auf eine linke Klammer "(". In diesem Fall schieben wir diese einfach auf den Operator-Stapel. (2) Wir stoßen auf eine Zahl: Sie wird auf den Werte-Stapel gelegt. (3) Wir stoßen auf einen Operator. Nun holen wir alle Operatoren vom Operator-Stapel, die eine höhere oder gleich große Priorität haben wie der eben gefundene, und wenden diese auf die obersten Zahlen auf dem Werte-Stapel an (mit der Funktion rechne im Programm). Das Ergebnis dieser Operation wird wieder auf den Werte-Stapel zurückgelegt. Dies wird solange wiederholt, bis wir auf eine linke Klammer "(" oder einen Operator niederer Priorität treffen oder der Stapel leer ist. Anschließend wird der gefundene Operator auf den Operator-Stapel geschoben. (4) Wir stoßen auf eine rechte Klammer ")". Nun werden alle Operatoren vom Operator-Stapel geholt und auf die obersten Zahlen im Werte-Stapel angewandt (s. Punkt 3), bis wir auf eine linke Klammer stoßen. Diese wird dann vom Stapel entfernt. (5) Der Eingabestring ist zu Ende. In diesem Fall führe dasselbe wie in Punkt (4) aus, nur daß nicht auf eine linke Klammer gewartet wird, sondern auf das Stapelende.

Dieser wohl nicht allzu schwer zu programmierende Algorithmus übernimmt die vollständige Umwandlung von Infix-Code in Postfix-Code und führt quasi gleichzeitig dessen Berechnung durch. Besprechen wir nun die einzelnen Punkte nocheinmal kurz durch.

Punkt 1 ist leicht verständlich, da wir uns ja den Beginn einer neuen Klammerebene merken müssen. Alle Operatoren auf dem Stapel, die hinter "(" stehen bis zur nächsten Klammer, gehören in dieselbe Klammerebene. Punkt 2 ist insofern einsichtlich, daß wir unsere Zahlen ja irgendwo ablegen müssen, um später die einzelnen Operatoren darauf anwenden zu können. Die Reihenfolge ihrer Abarbeitung wird durch das Auftreten der Operatoren geregelt.

In Punkt 3 kommen jetzt die verschiedenen Prioritäten der Operatoren zum Tragen. Es erscheint vollkommen einleuchtend, daß alle Operatoren mit höherer Priorität zuerst abgearbeitet und deshalb auch vorher der Funktion berechne zugeführt werden müssen. Auch die Operatoren gleicher Priorität müssen vorher abgearbeitet werden, denn die Ausdrücke sollen ja von links nach rechts ausgewertet werden (Linksassoziativität). Logischerweise muß deshalb in 5*7/3 das 5*7 vor der Division ausgeführt werden. Soll ein Operator von rechts nach links ausgewertet werden, dürfen bei diesem nur die Operatoren höherer Priorität vom Stapel geholt werden.

Punkt 4 regelt dann nur mehr das Schließen einer Klammerebene, damit auch alle Operatoren angewandt werden, die bis jetzt aufgrund ihrer Priorität zurückstanden. Punkt 5 erledigt dasselbe für die äußerste (nicht geklammerte) Ebene.

In der Praxis sieht dieser Algorithmus wie in Listing 2 aus, welches die Konvertierung von Infix nach Postfix mit gleichzeitiger Berechnung für solche Terme übernimmt, welche sich aus +, -, *, /, ^ und (, ) zusammensetzen dürfen. Der Operator - verdient noch unsere besondere Aufmerksamkeit, denn er kann zwei verschiedene Bedeutungen einnehmen. Einerseits kann es sich hierbei um eine Subtraktion zweier Zahlen handeln, andererseits könnte er aber auch für ein negatives Vorzeichen stehen (Negationsoperator). Während es sich bei der Subtraktion um einen binären Operator handelt, d.h. daß er sich auf zwei Zahlen bezieht, stellt der Negationsoperator einen unären Operator dar. Dementsprechend müssen bei der Subtraktion zwei Zahlen vom Werte-Stapel geholt, die Differenz gebildet und das Ergebnis wieder zurückgeschoben werden, während die Negation nur eine Zahl vom Stapel holt, deren Vorzeichen umdreht und diese anschließend wieder zurückschiebt. Damit das Programm merkt, ob es sich bei einem auf dem Operator-Stapel befindlichen Operator um eine Subtraktion oder eine Negation handelt, werden in Listing 2 alle "-", die einen Negationsoperator darstellen sollen, durch ein Underline "_" ersetzt. Wie stellt das Programm aber fest, welches Minus im Infix-String nun durch ein "_" ersetzt werden muß? Dazu wird das Umfeld des Zeichens genauer überprüft. Steht das Minus ganz am Anfang des Strings oder befindet sich ein "(" genau vor dem Minus, handelt es sich um eine Negation, sonst ist es eine Subtraktion.

Mithilfe von Listing 2 können Sie den Komfort Ihrer Programme erheblich verbessern. Sie brauchen nur den String mit dem zu berechnenden Term der Funktion berechne übergeben und erhalten das Ergebnis als double zurück. Ein eventueller Fehler im Term kann dadurch festgestellt werden, daß die globale Variable calcerr einen Wert ungleich null enthält. In diesem Fall ist der Rückgabewert sinnlos. Das bestehende Programm notfalls um Winkelfunktionen oder logische Operatoren zu erweitern sollte nicht schwerfallen. In manchen Fällen, wenn die Geschwindigkeit der Berechnung eine entscheidende Bedeutung spielt (z.B. bei Kalkulationssoftware), wäre es angebracht, die Umwandlung von Infix nach Postfix von der eigentlichen Berechnung des Postfix-Codes zu trennen. So könnten die Terme schon bei der Eingabe in Postfix-Notation umgewandelt werden und bei jeder Neuberechnung müßte nur mehr diese ausgewertet werden. Um dies zu bewerkstelligen, brauchen Sie eine heterogene Liste. Diese müßte in der Lage sein, sowohl Zahlen als auch Operatoren zu speichern. Nun brauchen Sie nur noch alle Aufrufe der rechne-Routine durch eine Prozedur zu ersetzen, die die Operanden vom Werte-Stapel holt und in die Liste einträgt, gefolgt vom Operator. Um diesen in der Liste gespeicherten Postfix-Ausdruck zu berechnen, gehen Sie sie am besten Knoten für Knoten durch. Treffen Sie auf eine Zahl, kommt sie auf den Werte-Stapel, bei einem Operator wird rechne mit dem jeweiligen Operator als Argument aufgerufen.

Damit wollen wir das Kapitel Stapel und Schlangen aber vorläufig abschließen. Wir wollen uns hingegen wieder dem Problem der Speicherung von Schlüsseln und deren schnellen Wiederfindung widmen. Dazu werden wir in der nächsten Folge eine neue Datenstruktur kennenlernen, die als Ersatz für eine verkettete Speicherung linearer Listen dienen kann. Im Gegensatz dazu erlaubt sie aber einen viel schnelleren Suchvorgang. Lassen Sie sich also überraschen!

Kursübersicht:

Teil 1 -- Einführung und lineare Listen.
Teil 2 -- Der Stapel und seine Anwendung.
Teil 3 -- Der Baum.
Teil 4 -- Anwendung von Bäumen.
Teil 5 -- Hashverfahren
Teil 6 -- Sortieren

Markus Öllinger ...........

Listing 2-1.c

Listing 2-1.h

Listing 2-2.c

Alle Listings mit richtigen Dateinamen (shift-click!)

....